/**
 * @author dingyue.zhf
 * @description 基于状态机二叉搜索树的序列化和反序列化
 */

/**
 * 序列化
 *
 * 确定一种遍历方式，这次的分隔符会复杂一些,()
 * 1. 用前序遍历
 * 2. 用括号包裹叶子节点
 * 3. 用逗号分隔相邻节点
 * 3(1(,3),4(,5))
 *
 * 主要是为了学习状态机
 * 这种方式可以类推到html字符串转树形结构
 *
 * 需要包含一些空节点
 *
 * 需要考虑极限情况，有一些节点是空的，要么序列化时过滤掉，要么解析时处理特殊情况
 */
var serialize = (root) => {
  const getChilren = () => (root.left || root.right ? `(${serialize(root.left)},${serialize(root.right)})` : '');
  // 先序遍历
  return root ? `${root.val}${getChilren()}` : '';
};

/**
 * 反序列化
 */
var deserialize = (str) => {
  let idx = 0,
    scode = 0,
    root = null,
    p,
    /**
     * 0 当前节点
     * 1 左节点
     * 2 右节点
     */
    k = 0;
  const stack = [];

  while (idx < str.length) {
    switch (scode) {
      // 状态管理
      case 0: {
        if (str[idx] >= '0' && str[idx] <= '9') {
          scode = 1;
        } else if (str[idx] === '(') {
          scode = 2;
        } else if (str[idx] === ',') {
          scode = 3;
        } else if (str[idx] === ')') {
          scode = 4;
        }
        break;
      }

      // 处理字符串
      case 1: {
        let s = '';
        // 重置字符串
        while (idx < str.length && str[idx] >= '0' && str[idx] <= '9') {
          s += str[idx];
          idx++;
        }
        const val = parseInt(s);
        p = new TreeNode(val);
        if (!root) {
          root = p;
        } else if (k === 1) {
          stack[stack.length - 1].left = p;
        } else if (k === 2) {
          stack[stack.length - 1].right = p;
        }
        scode = 0;
        break;
      }
      // 处理左括号 入栈
      case 2: {
        // 入栈
        stack.push(p);
        // 指向左节点
        k = 1;
        idx++;
        scode = 0;
        break;
      }
      // 处理逗号
      case 3: {
        // 指向右节点
        k = 2;
        idx++;
        scode = 0;
        break;
      }
      // 处理右括号 出栈
      case 4: {
        stack.pop();
        idx++;
        scode = 0;
        break;
      }
      default:
        break;
    }
  }
  return root;
};
